package com.fanpan26.algo.sort;

import java.util.Arrays;

/**
 * @author fanpan26
 */
public class CountingSort {
    public static void main(String[] args) {
        int[] arr = new int[]{8,7,9,6,7,5,4,8,7,6,6,6,7,3,2,3,4,5,4,4,4,6,5,8};
        sort1(arr,arr.length);
    }

    private static void sort(int[] a,int n){
        if (n<=1) {
            return;
        }

        //把MAX找出来
        int max = 0;
        for (int i=0;i<n;i++){
            if(a[i]>max){
                max = a[i];
            }
        }
        //新生成一个max长度的数组
        int[] c = new int[max+1];
        for (int i=0;i<=max;i++){
            c[i]=0;
        }

        //遍历数组，将值放入max数组中
        for (int i=0;i<n;i++){
            c[a[i]]++;
        }
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(c));

        for (int i=1;i<=max;i++){
            c[i]=c[i-1]+c[i];
        }
        System.out.println(Arrays.toString(c));

        int[] r = new int[n];
        for (int i=n-1;i>=0;i--){
            int index = c[a[i]]-1;
            r[index]=a[i];
            c[a[i]]--;
        }
        System.out.println(Arrays.toString(r));

    }

    private static void sort1(int[] a,int n){
        if (n<=1){
            return;
        }
        //先求出max
        int max = 0;
        for (int i=0;i<n;i++){
            if (a[i]>max){
                max = a[i];
            }
        }
        //初始化max + 1长度的数组
        int[] c = new int[max+1];
        for (int i=0;i<c.length;i++){
            c[i] = 0;
        }
        //遍历数组，将每个值 计数，每个索引是数组元素，索引上的值是计数个数
        for (int i=0;i<n;i++){
            c[a[i]]++;
        }
        System.out.println(Arrays.toString(c));
        //遍历数组，计算总数
        for (int i=1;i<=max;i++){
            c[i]=c[i-1]+c[i];
        }
        System.out.println(Arrays.toString(c));
        //遍历数组，求出新的排名
        int[] r = new int[n];
        for (int i=0;i<n;i++){
            int index = c[a[i]] -1;
            c[a[i]]--;
            r[index] = a[i];
        }
        System.out.println(Arrays.toString(r));

    }
}
